import com.sun.source.tree.Tree;

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {


    }

    //子集
    List<List<Integer>> ret;
    List<Integer> path;
    //解法1
//    public List<List<Integer>> subsets(int[] nums){
//        ret = new ArrayList<>();
//        path = new ArrayList<>();
//        dfs(nums,0);
//        return ret;
//    }
//    public void dfs(int[] nums, int pos){
//        if (pos == nums.length) {
//            ret.add(new ArrayList<>(path));
//            return;
//        }
//        //选
//        path.add(nums[pos]);
//        dfs(nums,pos+1);
//        path.remove(path.size()-1);
//        //不选
//        dfs(nums,pos+1);
//    }
    //解法2
    public List<List<Integer>> subsets(int[] nums){
        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs(nums,0);
        return ret;
    }
    public void dfs(int[] nums, int pos){
        ret.add(new ArrayList<>(path));

        for (int i = pos; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(nums,i+1);
            path.remove(path.size()-1);//恢复现场
        }
    }


    //全排列
    List<List<Integer>> ret3;
    List<Integer> path1;
    boolean[] check;
    public List<List<Integer>> permute(int[] nums){
        ret3 = new ArrayList<>();
        path1 = new ArrayList<>();
        check = new boolean[nums.length];
        dfs(nums);
        return ret3;
    }
    public void dfs(int[] nums){
        if (nums.length == path1.size()){
            ret3.add(new ArrayList<>(path1));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (check[i] == false){
                path1.add(nums[i]);
                check[i] = true;
                dfs(nums);
                check[i] = false;
                path1.remove(path1.size()-1);
            }
        }
    }


    //二叉树的所有路径
    List<String> ret2;
    public List<String> binaryTreePaths(TreeNode root){
        ret2 = new ArrayList<>();
        dfs(root,new StringBuffer());
        return ret2;
    }
    public void dfs(TreeNode root, StringBuffer _path){
        StringBuffer path = new StringBuffer(_path);
        path.append(Integer.toString(root.val));
        if (root.left ==null && root.right==null){
            ret2.add(path.toString());
            return;
        }
        path.append("->");
        if (root.left != null) dfs(root.left,path);
        if (root.right != null) dfs(root.right,path);
    }

    //二叉搜索树中第k小的元素
    int count;
    int ret1;
    public int kthSmallest(TreeNode root,int k){
        count = k;
        dfs(root);
        return ret1;
    }
    public void dfs(TreeNode root){
        if (root == null || count == 0) return;

        dfs(root.left);
        if (count == 0) return;

        count--;
        if (count == 0) ret1 = root.val;
        if (count == 0) return;
        dfs(root.right);
    }



    //验证二叉搜索树
    long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root){
        if (root == null) return true;
        boolean left = isValidBST(root.left);
        //剪枝
        if (left == false) return false;

        boolean cur = false;
        if (root.val >prev) cur = true;
        //剪枝
        if (cur == false) return false;
        prev = root.val;
        boolean right = isValidBST(root.right);
        return left && cur && right;
    }

    //二叉树剪枝
    public  TreeNode pruneTree(TreeNode root){
        if (root == null) return null;

        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.left ==null && root.right == null && root.val == 0){
            root = null;
        }
        return root;
    }

    //求根节点到叶节点数字之和
    public int sumNumbers(TreeNode root){
        return dfs(root,0);
    }
    public int dfs(TreeNode root,int preSum){
        preSum = preSum*10 + root.val;
        if (root.left == null && root.right == null){
            return preSum;
        }
        int ret = 0;
        if (root.left != null) ret += dfs(root.left,preSum);
        if (root.right != null) ret +=dfs(root.right,preSum);
        return ret;
    }


    //计算布尔二叉树的值
    public boolean evaluateTree(TreeNode root){
        if (root.left == null) return root.val==0 ? false : true;

        boolean left = evaluateTree(root.left);
        boolean right = evaluateTree(root.right);
        return root.val == 2 ? left | right : left & right;
    }

    public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode() {}
  TreeNode(int val) { this.val = val; }
  TreeNode(int val, TreeNode left, TreeNode right) {
  this.val = val;
  this.left = left;
  this.right = right;
  }
  }

    //POW(x,n)-快速幂
    public double myPow(double x, int n){
        return n<0 ? 1.0/pow(x,-n) :pow(x,n);
    }
    public double pow(double x, int n){
        if (n == 0) return 1;
        double tmp = pow(x,n/2);
        return n%2 == 0 ? tmp*tmp : tmp*tmp*x;
    }

    //两两交换链表中的节点
    public ListNode swapPairs(ListNode head){
        if (head == null || head.next == null) return head;

        ListNode tmp = swapPairs(head.next.next);
        ListNode ret = head.next;
        ret.next = head;
        head.next = tmp;

        return ret;
    }


    //反转链表
    public ListNode reverseList(ListNode head){

        if (head == null || head.next == null) return head;

        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return newHead;
    }

    //合并两个有序链表
    public class ListNode {
  int val;
  ListNode next;
  ListNode() {}
  ListNode(int val) { this.val = val; }
  ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2){
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        if (l1.val <l2.val){
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }else{
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }

    //汉诺塔
    public void hanota(List<Integer> A,List<Integer> B,List<Integer> C){
        dfs(A,B,C,A.size());
    }
    public void dfs(List<Integer> a,List<Integer> b,List<Integer> c,int n){
        if (n == 1){
            c.add(a.remove(a.size()-1));
            return;
        }
        dfs(a,c,b,n-1);
        c.add(a.remove(a.size()-1));
        dfs(b,a,c,n-1);
    }
}